The typical CAM is illustrated in FIG. 1. An input number of width w (101) is compared against a table of allowed values (102). If there is a match, the location of the matched word (103) is returned. If the list of allowed values is 2n long, the CAM has to contain a minimum of 2n×w bits of memory along with comparators, also 2n×w in number.
It is also possible to perform the function of the CAM using a Random Access Memory, or RAM, using 2w×n bits of RAM, as shown in FIG. 2. The input number 201 is used to address a location in the memory 202 which contains the index 203 for that number, if it is in the list of allowed values. If the number is not in the list the corresponding index is value is set to some special value indicating no-match.
CAMs are expensive since each cell contains a memory element as well as a comparison circuit. Obtaining equivalent functionality with RAMs may require significantly more memory when the numbers are very wide.
The present invention improves upon these conventional CAMs. The system and method disclosed here can compare inputs of width w against a list of length up to 2w using only about 2w bits of RAM. As a result, considerable cost savings are possible compared to previous implementations. Number ranges and arbitrary groupings of numbers are possible using extensions of the methods of the disclosure. The application of this invention extends beyond searches and lookups. For example, the method could be used to compress symbols in a communication stream.